package top.humbleyuan.leet;

import org.junit.Test;
import org.omg.PortableInterceptor.INACTIVE;
import top.humbleyuan.leet.datastructure.linkedlist.LinkNode;

import java.util.*;
import java.util.LinkedList;

/**
 * @Author HumbleYuan
 * @Date 2020/4/25 15:05
 * @Des
 */
public class Synthesize_2 {

    /**
     * 颜色分类
     */
    @Test
    public void leet_75() {
        int[] nums = {2,0,2,1,1,0};

        // 双指针,分别记录前后第一个不是0和1的index
        int curZeroIndex = 0;
        int curTwoIndex = nums.length - 1;

        for(int i = 0;i < nums.length; i++) {

            if((nums[i] == 0) && (i == curZeroIndex)) {
                curZeroIndex++;
                continue;
            }

            if((nums[i] == 2) && (i > curTwoIndex)) {
                break;
            }

            // 和最前面不是0的交换
            if(nums[i] == 0 && i != curZeroIndex) {
                int temp = nums[i];
                nums[i] = nums[curZeroIndex];
                nums[curZeroIndex++] = temp;
                i--;
            }

            if(nums[i] == 2 && i != curTwoIndex) {
                int temp = nums[i];
                nums[i] = nums[curTwoIndex];
                nums[curTwoIndex--] = temp;
                i--;
            }

        }

        System.out.println(Arrays.toString(nums));
    }

    /**
     * 集合子集
     */
    @Test
    public void leet78() {
        int[] nums = {1,2,3};

        List<List<Integer>> res = new ArrayList<>();

        // 回溯
        leet78_dfs(nums, new ArrayList<>(), res, 0);
        System.out.println(res.toString());
    }

    public static void leet78_dfs(int[] nums, List<Integer> list, List<List<Integer>> res, int index) {
        if(nums.length == index) {
            return;
        }

        for (int i = index; i < nums.length; i++) {
            list.add(nums[i]);
            res.add(new ArrayList<>(list));

            // dfs
            leet78_dfs(nums, list, res, ++index);

            // 回溯
            list.remove(list.size() - 1);
        }

        return;

    }

    /**
     * 搜索单词
     * dfs + 回溯
     *
     * 需要优化代码
     */
    @Test
    public void leet_79() {
        Character[][] cha = { {'A','B','C','E'},
                {'S','F','C','S'},
                {'A','D','E','E'}};
        String key = "ABCCED";
        String cur = "";

        int[][] begin = new int[1][2];
        boolean[][] f = new boolean[cha.length][cha[0].length];

        for (int i = 0; i < cha.length; i++) {
            for (int j = 0; j < cha[0].length; j++) {

                /**
                 * 首个字符判定，后面可以优化到dfs一起
                 */
                begin[0][0] = i;
                begin[0][1] = j;
                cur += cha[i][j];

                if(cur.equals(key)) {
                    System.out.println("true");
                    return;
                }

                // 剪枝
                if(!cur.equals(key.substring(0, cur.length()))) {
                    continue;
                }

                f[i][j] = true;
                if(leet_79_dfs(key, cha, begin,
                        f, cur)) {
                    System.out.println("true");
                    return;
                }

                cur = "";
                f = new boolean[cha.length][cha[0].length];
            }
        }

        System.out.println("false");
    }

    public boolean leet_79_dfs(String key, Character[][] cha, int[][] curPoint, boolean[][] exist, String cur) {
        int rowIndex;
        int colIndex;

        // curPoint可以往上下左右四个方向
        for (int i = 0; i < 4; i++) {
            switch (i) {
                case 0:
                    curPoint[0][0] += 1;
                    break;
                case 1:
                    curPoint[0][0] -= 1;
                    break;
                case 2:
                    curPoint[0][1] += 1;
                    break;
                case 3:
                    curPoint[0][1] -= 1;
                    break;
            }

            rowIndex = curPoint[0][0];
            colIndex = curPoint[0][1];
            // 剪枝
            if(!(rowIndex >= 0 && rowIndex < cha.length) ||
                    !(colIndex >= 0 && colIndex < cha[0].length) || exist[rowIndex][colIndex]) {

            } else {
                cur += cha[rowIndex][colIndex];

                // 剪枝
                if(!cur.equals(key.substring(0, cur.length()))) {
                    cur = cur.substring(0, cur.length() - 1);
                } else {
                    //System.out.println(cur);
                    exist[rowIndex][colIndex] = true;
                    if(cur.equals(key) || leet_79_dfs(key, cha, curPoint, exist, cur)) {
                        return true;
                    }
                    cur = cur.substring(0, cur.length() - 1);
                    exist[rowIndex][colIndex] = false;
                }

            }

            // 回溯
            switch (i) {
                case 0:
                    curPoint[0][0] -= 1;
                    break;
                case 1:
                    curPoint[0][0] += 1;
                    break;
                case 2:
                    curPoint[0][1] -= 1;
                    break;
                case 3:
                    curPoint[0][1] += 1;
                    break;
            }
        }

        return false;

    }

    /**
     * 重排队列
     */
    @Test
    public void leet_406() {
        int[][] people = {{7,0}, {4,4}, {7,1}, {5,0}, {6,1}, {5,2}};

        /**
         * # 高度相同按序号排就行
         * # 高度不同先排高的
         */

        Arrays.sort(people, (a1, a2) -> a1[0] == a2[0] ? a1[1] - a2[1] : a2[0] - a1[0]);

        // 按顺序插入
        LinkedList<int[]> list = new LinkedList<>();

        for (int i = 0; i < people.length; i++) {
            list.add(people[i][1], people[i]);
        }

        int[][] res = new int[people.length][2];
        int i = 0;
        for (int[] arr : list) {
            res[i++] = arr;
        }

    }


    /**
     * 单词拆分
     */
    @Test
    public void leet_139() {
//        String s = "leetcode";
//        ArrayList<String> wordDict = new ArrayList<>();
//        wordDict.add("leet");
//        wordDict.add("code");

        String s = "catsandog";
        ArrayList<String> wordDict = new ArrayList<>();
        wordDict.add("cats");
        wordDict.add("dog");
        wordDict.add("sand");
        wordDict.add("and");
        wordDict.add("cat");

        HashSet<String> set = new HashSet<>(wordDict);
        Boolean[] memo = new Boolean[s.length()];

        // 回溯dfs
        Boolean res = leet_139_dfs(s, 0, set, memo);
        System.out.println(res);
    }

    /**
     * memo记录从字符串中第i个开始之后的字符串是否满足条件
     * @param s
     * @param begin
     * @param cur
     * @param memo
     * @return
     */
    public boolean leet_139_dfs(String s,int begin, HashSet<String> dic, Boolean[] memo) {
        if(begin == s.length()) {
            memo[begin] = true;
            return true;
        }

        // 如果有记录直接从记录里找
        if(memo[begin] != null) {
            return memo[begin];
        }

        for (int end = begin + 1; end < s.length(); end++) {

            // 找到匹配前缀了，进行下一部分的递归
            if(dic.contains(s.substring(begin, end)) && leet_139_dfs(s, end, dic, memo)) {
                memo[begin] = true;
                return true;
            }

        }

        memo[begin] = false;
        return false;

    }


    /**
     * 岛屿问题
     * 广度遍历循环bfs
     */
    @Test
    public void leet_200() {
        char[][] nums = {{'1','1','0','0','0'},{'1','1','0','0','0'},{'0','0','1','0','0'},{'0','0','0','1','1'}};

        if(nums == null || nums.length == 0 || nums[0].length == 0) {
            System.out.println(0);
            return;
        }

        boolean[][] flag = new boolean[nums.length][nums[0].length];

        int count = 0;

        // 向左向右拓展，用栈存之前的点
        for (int i = 0; i < nums.length; i++) {
            int x, y;
            for (int j = 0; j < nums[i].length; j++) {

                if(nums[i][j] == '1') {
                    count ++;
                    Queue<String> queue = new LinkedList<>();

                    nums[i][j] = '0';
                    queue.offer(i + "," + j);
                    while (!queue.isEmpty()) {
                        String[] loc = queue.poll().split(",");
                        int a = Integer.valueOf(loc[0]);
                        int b = Integer.valueOf(loc[1]);

                        // 上下左右
                        x = a;
                        y = b + 1;
                        if(y < nums[i].length && nums[x][y] == '1') {
                            nums[x][y] = '0';
                            queue.offer(x + "," + y);
                        }

                        x = a;
                        y = b - 1;
                        if(y >= 0 && nums[x][y] == '1') {
                            nums[x][y] = '0';
                            queue.offer(x + "," + y);
                        }

                        x = a - 1;
                        y = b;
                        if(0 <= x && nums[x][y] == '1') {
                            nums[x][y] = '0';
                            queue.offer(x + "," + y);
                        }

                        x = a + 1;
                        y = b;
                        if(x < nums.length && nums[x][y] == '1') {
                            nums[x][y] = '0';
                            queue.offer(x + "," + y);
                        }
                    }
                }
            }
        }

        System.out.println(count);
    }


    /**
     * 岛屿问题
     * dfs
     */
    @Test
    public void leet_200_2() {
        char[][] nums = {{'1','1','0','0','0'},{'1','1','0','0','0'},{'0','0','1','0','0'},{'0','0','0','1','1'}};

        if(nums == null || nums.length == 0 || nums[0].length == 0) {
            System.out.println(0);
            return;
        }

        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < nums[i].length; j++) {
                if(nums[i][j] == '1') {
                    count++;

                    leet200_dfs(nums, i, j);
                }
            }
        }

        System.out.println(count);
    }

    public void leet200_dfs(char[][] nums, int x, int y) {
        if(x < 0 || x >= nums.length || y < 0 || y >= nums[0].length || nums[x][y] == '0') {
            return;
        }

        nums[x][y] = '0';
        // dfs
        leet200_dfs(nums, x, y - 1);
        leet200_dfs(nums, x, y + 1);
        leet200_dfs(nums, x - 1, y);
        leet200_dfs(nums, x + 1, y);

    }


    /**
     * 乘积最大子数组
     */
    @Test
    public void leet_152() {
        /**
         * 可以以0为界分成多个子数组，求子数组的最大乘积并取最大值
         * 子数组中最大乘积是从前往后和从后往前都要比一遍
         */

        // 用curSum存当前所有数乘积, sum是最大乘积
        int sum = Integer.MIN_VALUE;
        int curSum = 1;
        int[] nums = {-2, 0, -1};
        for (int num : nums) {
            curSum *= num;
            if(curSum > sum) {
                sum = curSum;
            }

            // 当遇到0断开,curSum变成0
            if(num == 0) {
                curSum = 1;
            }
        }

        curSum = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            curSum *= nums[i];
            if(curSum > sum) {
                sum = curSum;
            }

            // 当遇到0断开,curSum变成0
            if(nums[i] == 0) {
                curSum = 1;
            }
        }

        System.out.println(sum);

    }

    /**
     * 多数元素
     */
    public void leet_169() {
        HashMap<Integer, Integer> map = new HashMap<>();

        int[] nums = {3, 2, 3, 3};
        int i;
        for (i = 0; i < nums.length; i++) {
            int num = map.getOrDefault(nums[i], 0);

            map.put(nums[i], num + 1);
            if((num + 1) > nums.length / 2) {
                System.out.println(nums[i]);
                return;
            }
        }

        System.out.println(nums[i - 1]);
    }

    /**
     * 排序矩阵查找
     */
    @Test
    public void leet_10_09() {
        // 类似二分法
        int[][] nums = {
            {1,   4,  7, 11, 15},
            {2,   5,  8, 12, 19},
            {3,   6,  9, 16, 22},
            {10, 13, 14, 17, 24},
            {18, 21, 23, 26, 30}
        };

        int target = 100;

        /**
         * 根据结构确定思路：
         * 每次和一个数比较时
         * 所以可以从右上角或者左下角开始逐步剔除行或列
         */
        // 从右上角开始
        int curI = 0;
        int curJ = nums[0].length - 1;

        while(curI < nums.length && curJ >= 0) {
            if(nums[curI][curJ] == target) {
                System.out.println(true);
                return;
            }

            if(nums[curI][curJ] > target) {
                curJ--;
                continue;
            }

            if(nums[curI][curJ] < target) {
                curI++;
            }
        }

        System.out.println(false);

    }

    /**
     * 搜索二维矩阵
     */
    @Test
    public void leet_74() {
        /**
         * 先二分找到所在行，再二分进行行内搜索
         */

//        int[][] matrix = {
//                {1,   3,  5,  7},
//                {10, 11, 16, 20},
//                {23, 30, 34, 50}
//        };

        int[][] matrix = {{-9,-9,-9,-8,-8,-7,-6,-4,-4,-3},
                {0,1,2,2,4,5,5,5,7,9},
                {12,12,14,14,15,17,19,19,19,21},
                {22,23,23,25,25,26,26,28,28,29},
                {31,31,31,33,34,36,37,38,38,39},
                {40,42,43,44,46,46,46,47,49,50},
                {52,54,55,57,59,60,60,62,64,66},
                {68,68,70,71,71,72,74,76,78,80},
                {82,83,85,85,85,87,88,88,89,89},
                {90,90,90,91,93,94,94,95,95,97},
                {98,98,99,99,101,103,105,106,108,109},
                {112,112,112,113,113,113,114,116,118,118},
                {119,121,122,124,125,125,125,126,127,128},
                {131,133,134,134,134,135,135,137,137,139},{141,143,145,147,148,150,150,150,150,152},{153,153,154,155,157,157,157,159,161,162},{164,166,167,167,167,169,170,170,171,173},{176,176,178,179,181,182,183,183,184,186}};

        int target = 135;

        int pre = 0, back = matrix.length - 1;
        int maxCol = matrix[0].length - 1;

        // 和一般二分不同，先逼近到两个相邻行
        while(pre < back - 1) {
            int mid = (back- pre) / 2 + pre;
            if(matrix[mid][maxCol] == target) {
                System.out.println(true);
                return;
            }

            if(matrix[mid][maxCol] > target) {
                back = mid;
            } else {
                pre = mid;
            }
        }

        // 两行判断
        if(matrix[pre][maxCol] == target || matrix[back][maxCol] == target) {
            System.out.println(true);
            return;
        }

        int row;
        if(target < matrix[pre][maxCol]) {
            row = pre;
        } else {
            row = back;
        }

        pre = 0;
        back = matrix[row].length - 1;
        while(pre <= back) {
            int mid = (back- pre) / 2 + pre;
            if(matrix[row][mid] == target) {
                System.out.println(true);
                return;
            }

            if(matrix[row][mid] > target) {
                back = mid - 1;
            } else {
                pre = mid + 1;
            }
        }

        System.out.println(false);

    }




}
